We give an explicit extension of Spencer's result on the biplanar crossingnumber of the Erdos-Renyi random graph $G(n,p)$. In particular, we show thatthe k-planar crossing number of $G(n,p)$ is almost surely $\Omega((n^2p)^2)$.Along the same lines, we prove that for any fixed $k$, the $k$-planar crossingnumber of various models of random $d$-regular graphs is $\Omega ((dn)^2)$ for$d > c_0$ for some constant $c_0=c_0(k)$.
展开▼
机译：我们在Erdos-Renyi随机图$ G（n，p）$的双平面交叉数上给出Spencer结果的显式扩展。特别地，我们证明了$ G（n，p）$的k平面交叉数几乎肯定是$ \ Omega（（n ^ 2p）^ 2）$。沿着相同的线，我们证明了对于任何固定的$ k $，对于某些常数$ c_0 = c_0（k）$，$ d $-正则图的各种模型的$ k $-平面交叉数为$ \ Omega（（dn）^ 2）$ for $ d> c_0 $。
展开▼
